package tree;

/**题目：二叉搜索树查找节点
 *
 * @Author Gavin
 * @date 2022.01.05 21:46
 */
public class tree_16 {
    /**
     * 解题思路：二叉搜索数的特点，左子树小于根节点，右子树大于根节点
     * 子树也是二叉搜索树
     */
    //第一种递归方法 Time:O(h) Space:O(h)
    public TreeNode solution_1(TreeNode root,int val){
        if(root==null||val==root.val)return root;
        else if(root.val>val) return solution_1(root.left,val);
        else return solution_1(root.right,val);
    }
    //第二种方法：迭代 Time:O(h) Space:O(1)
    public TreeNode solution_2(TreeNode root,int val){
        while (root!=null&&root.val!=val){
            if(val<root.val)root=root.left;
            else root=root.right;
        }
        return root;
    }
}
